using System;
using System.Collections.Generic;
using System.Linq;
using ParserGenerator.Extensions;

namespace ParserGenerator.TableCompression
{
    [Serializable]
    internal sealed class CompactTableConstructor
    {
        private readonly int _columns;
        private readonly CompactTableRow[] _rows;
        private readonly CompactTableRow[] _sortedRows;
        private readonly int[] _baseArray;
        private readonly List<int> _check = new List<int>();
        private readonly List<int> _value = new List<int>();
        private readonly HashSet<int> _used = new HashSet<int>();

        public CompactTableConstructor(CompactTableBuilder builder)
        {
            if (builder == null)
                throw new ArgumentNullException(nameof(builder));
            _columns = builder.Columns;
            _rows = new CompactTableRow[builder.Rows.Count];
            for (int i = 0; i < _rows.Length; i++)
            {
                CompactTableCell[] cells = builder.Rows[i].Cells.ToArray();
                Array.Sort(cells);
                _rows[i] = new CompactTableRow(i, cells.AsReadOnly());
            }
            _sortedRows = new CompactTableRow[_rows.Length];
            _rows.CopyTo(_sortedRows, 0);
            Array.Sort(_sortedRows);
            _baseArray = new int[_rows.Length];
        }

        private CompactTableRow MatchRow(int j)
        {
            CompactTableRow y = _sortedRows[j];
            for (int i = j - 1; i >= 0; i--)
            {
                CompactTableRow x = _sortedRows[i];
                if (!x.RangeEquals(y))
                    return null;
                if (x.Equals(y))
                    return x;
            }
            return null;
        }

        private int FindPlace(CompactTableRow row)
        {
            int place = 0;
            while (true)
            {
                while (_used.Contains(place))
                    place++;
                while (place + _columns - 1 >= _check.Count)
                {
                    _check.Add(-1);
                    _value.Add(-1);
                }
                int k;
                for (k = 0; k < row.Size; k++)
                    if (_check[place + row.Cells[k].Column] != -1)
                        break;
                if (k >= row.Size)
                    return place;
                place++;
            }
        }

        private static double RedirectNegative(List<int> list, int target)
        {
            if (list.Count <= 0)
                return 1.0;
            int counter = 0;
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i] == -1)
                {
                    list[i] = target;
                    counter++;
                }
            }
            return 1.0 - (double)counter / list.Count;
        }

        public CompactTable Construct()
        {
            for (int j = 0; j < _sortedRows.Length; j++)
            {
                CompactTableRow y = _sortedRows[j];
                CompactTableRow x = MatchRow(j);
                if (x != null)
                    _baseArray[y.Number] = _baseArray[x.Number];
                else
                {
                    int place = FindPlace(y);
                    for (int k = 0; k < y.Size; k++)
                    {
                        int c = y.Cells[k].Column;
                        int v = y.Cells[k].Value;
                        _check[place + c] = c;
                        _value[place + c] = v;
                    }
                    _baseArray[y.Number] = place;
                    _used.Add(place);
                }
            }
            for (int i = _value.Count - 1; i >= 0; i--)
                if (_value[i] == -1)
                    _value.RemoveAt(i);
                else
                    break;
            double loadFactor = RedirectNegative(_check, _columns);
            RedirectNegative(_value, 0);
            CompactTable table = new CompactTable();
            table.Columns = _columns;
            table.LoadFactor = loadFactor;
            table.Rows = _rows.AsReadOnly();
            table.BaseArray = _baseArray.AsReadOnly();
            table.CheckArray = _check.ToArray().AsReadOnly();
            table.ValueArray = _value.ToArray().AsReadOnly();
            return table;
        }
    }
}
